package com.hy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:797. 所有可能的路径
 * <p>
 * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
 * graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
 *
 * User:Mr.Du
 * Date:2024/4/17
 * Time:19:51
 */
public class AllPathsSourceTarget {

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();

    /**
     * 查找图中从源节点到目标节点的所有路径。
     *
     * @param graph 表示图的邻接矩阵，graph[i][j] 表示节点 i 到节点 j 是否存在连接（1 表示存在，0 表示不存在）。
     * @return 返回一个包含所有从源节点到目标节点路径的列表，每个路径都以列表形式表示。
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        List<Integer>[] l = new List[n]; // 创建一个数组存储每个节点的路径
        boolean[] visited = new boolean[n]; // 标记节点是否被访问过
        for(int i = 0;i < n;i++){
            l[i] = new ArrayList<>(); // 初始化路径数组
        }
        int j = 0;
        for(int[] g : graph){
            for(int i : g){
                l[j].add(i); // 填充路径数组，按照邻接矩阵构建图的邻接表形式
            }
            j++;
        }
        list.add(0); // 从源节点开始递归搜索
        dfs(l, visited, 0, n - 1); // 深度优先搜索所有从源节点到目标节点的路径
        return res; // 返回所有找到的路径
    }

    public void dfs(List<Integer>[] l, boolean[] visited, int start, int n){
        if(start == n){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i : l[start]){
            if(!visited[i]){
                list.add(i);
                visited[i] = true;
                dfs(l, visited, i, n);
                list.removeLast();
                visited[i] = false;
            }
        }
    }

    public List<List<Integer>> allPathsSourceTarget1(int[][] graph) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0);
        travel(graph, 0, list);
        return res;
    }

    public void travel(int[][] graph, int i, LinkedList<Integer> list){
        if(i == graph.length - 1){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int j : graph[i]){
            list.add(j);
            travel(graph, j, list);
            list.removeLast();
        }

    }
}
